
//1172.餐盘栈
class DinnerPlates {
    priority_queue<int,vector<int>,greater<int>> pq;  //存储不满的栈
    vector<stack<int>> nums;  //存储所有的栈 
    int max_size;
public:
    DinnerPlates(int capacity) {
        max_size=capacity;
    }
    
    void push(int val) {
        if(!pq.empty()&&pq.top()>=nums.size())  //如果堆中最小值比数组长度大,说明堆中所有元素都不满足
        while(!pq.empty()) pq.pop();

        if(pq.empty())
        {
            //全部栈都是满的,在数组后面再加一个栈
            nums.push_back({});
            nums.back().push(val);
            if(nums.back().size()!=max_size) pq.push(nums.size()-1);
        }
        else
        {
            int pos=pq.top();
            nums[pos].push(val);
            if(nums[pos].size()==max_size) pq.pop();  //如果满了就将其移除堆
        }
    }
    
    int pop() {
        return popAtStack(nums.size()-1);
    }
    
    int popAtStack(int index) {
        if(nums.size()<=index||nums[index].empty()) return -1;
        
        int ret=nums[index].top();
        if(nums[index].size()==max_size) pq.push(index);
        nums[index].pop();
        while(nums.size()&&nums.back().empty()) nums.pop_back();    //如果最后一个栈为空,直接将其移除数组
    
        return ret;
    }
};

/**
 * Your DinnerPlates object will be instantiated and called as such:
 * DinnerPlates* obj = new DinnerPlates(capacity);
 * obj->push(val);
 * int param_2 = obj->pop();
 * int param_3 = obj->popAtStack(index);
 */